package com.mbatis.leeCode;

import org.junit.Test;

/**
 * @Classname LongCommonPrefix
 * @Date 2021/5/27 10:33  最长公共前缀
 * @Created by zhang.yuming
 */
public class LongCommonPrefix {

    // 方法一
    @Test
    public void strPrefix() {
        String string[] = {"flower", "flight", "flow"};
        if (string == null || string.length == 0) {
            System.out.println("没有数据");
        }
        String prefix = string[0];
        for (int i = 1; i < string.length; i++) {
            prefix = longCommonPrefixCheck(prefix, string[i]); // 用 str[0] 跟每一个字符串比较，取出重合的数据出来，然后用重合的数据跟下一个字符串比较
            if (prefix.length() == 0) {
                break;
            }
        }
        System.out.println("prefix=" + prefix);
    }

    private String longCommonPrefixCheck(String prefix, String s) {
        int length = Math.min(prefix.length(), s.length());
        int index = 0;
        // 这里比较后可以取出重合的数据返回给 prefix
        while (index < length && prefix.charAt(index) == s.charAt(index)) {
            index++;
        }
        return prefix.substring(0, index);
    }

    // 方法二 ：分治法 递归
    @Test
    public void lcpFenzhi() {
        String strs[] = {"flower", "flight", "flow", "float"};
        if (strs == null || strs.length == 0) {
            System.out.println("没有数据");
        }
        String prefix = lcp(strs, 0, strs.length - 1);
        System.out.println("prefix =" + prefix);
    }

    public String lcp(String[] strs, int start, int end) {
        if (start == end) {
            return strs[start];
        }
        int mid = (end - start) / 2 + start; // 中间值
        String ls = lcp(strs, start, mid);
        String rs = lcp(strs, mid + 1, end);
        return commonLcp(ls, rs);
    }

    // 求出公共前缀
    private String commonLcp(String ls, String rs) {
        int minLength = Math.min(ls.length(), rs.length());
        for (int i = 0; i < minLength; i++) {
            if (ls.charAt(i) != rs.charAt(i)) {
                return ls.substring(0,i);
            }
        }
        return ls.substring(0,minLength);
    }


    // 二分查找






}
